﻿using System;
using System.Collections.Generic;
using System.Text;

namespace AlgorithmTest
{
    public class T_0019_RemoveNthFromEnd
    {
        // 删除链表的倒数第N个节点

        // 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

        // 提示：
        //   链表中结点的数目为 sz
        //   1 <= sz <= 30
        //   0 <= Node.val <= 100
        //   1 <= n <= sz

        public void Test()
        {
            var list = new ListNode(1)
            {
                next = new ListNode(3)
                {
                    next = new ListNode(5)
                    {
                        next = new ListNode(9)
                    }
                }
            };
            var result = RemoveNthFromEnd(list, 2);
            while (result != null)
            {
                Console.WriteLine(result.val);
                result = result.next;
            }
            Console.Read();
        }

        // 先判断长度，再删除（略）

        // 双指针
        public ListNode RemoveNthFromEnd(ListNode head, int n)
        {
            ListNode l = head;
            ListNode r = head;
            for (int i = 0; i < n; i++)
            {
                r = r.next;
            }
            if (r == null)
                return head.next;
            while (r.next != null)
            {
                l = l.next;
                r = r.next;
            }
            l.next = l.next.next;
            return head;
        }

        // 递归
        public ListNode RemoveNthFromEnd1(ListNode head, int n)
        {
            int pos = Length(head, n);
            // 说明删除的是头节点
            if (pos == n)
                return head.next;
            return head;
        }

        // 获取节点所在位置，逆序
        public int Length(ListNode node, int n)
        {
            if (node == null)
                return 0;
            int pos = Length(node.next, n) + 1;
            //获取要删除链表的前一个结点，就可以完成链表的删除
            if (pos == n + 1)
                node.next = node.next.next;
            return pos;
        }
    }
}
